﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Security.Cryptography;

namespace SudokuGame
{
    /// <summary>
    /// 九宫数独类。
    /// </summary>
    public class Sudoku
    {
        #region 【常量】
        /// <summary>
        /// 数独的行数、列数。
        /// </summary>
        private const int SUDOKU_CONT = 9;
        #endregion

        #region 【字段】
        /// <summary>
        /// 数独难度级别。
        /// </summary>
        private readonly Level _level = 0;
        /// <summary>
        /// 待解的数独模板。
        /// </summary>
        private readonly int[,] _sudoku_template = null;
        /// <summary>
        /// 数独的终盘。
        /// </summary>
        private readonly int[,] _sudoku_end = null;
        /// <summary>
        /// 数独结果集。
        /// </summary>
        private int[,] _sudoku_result = null;
        #endregion
        
        #region 【属性】
        /// <summary>
        /// 获取数独的终盘。
        /// </summary>
        public int[,] SudokuEnd
        {
            get { return _sudoku_end; }
        }
        /// <summary>
        /// 获取或设置数独的结果集。
        /// </summary>
        public int[,] SudokuResult
        {
            get { return _sudoku_result; }
            set { _sudoku_result = value; }
        }
        /// <summary>
        /// 获取数独的初始盘面。
        /// </summary>
        public int[,] SudokuTemplate
        {
            get { return _sudoku_template; }
        }
        #endregion

        #region 【构造方法】
        /// <summary>
        /// 实例化一个随机数独。
        /// </summary>
        /// <param name="level">数独的级别。</param>
        public Sudoku(Level level)
        {
            this._level = level;
            this._sudoku_end = RandomSudoku();
            this._sudoku_template = this.DigHole(Convert.ToInt32(this._level) * 13, this._sudoku_end);
            this._sudoku_result = (int[,])this._sudoku_template.Clone();
        }

        /// <summary>
        /// 实例化一个数独。
        /// </summary>
        /// <param name="level">数独的级别。</param>
        /// <param name="sudoku_template"></param>
        public Sudoku(Level level,int[,] sudoku_template)
        {
            this._level = level;
            this._sudoku_template = sudoku_template;
            this._sudoku_result = (int[,])this._sudoku_template.Clone();
        }
        #endregion

        #region 【数独输出】
        /// <summary>
        /// 打印终盘数独盘面。
        /// </summary>
        public void PrintSudokuEnd()
        {
            if (this._sudoku_end == null)
            {
                Console.WriteLine("此数独未设置终盘。");
            }
            else
            {
                this.PrintSudoku(this._sudoku_end);
            }
        }

        /// <summary>
        /// 打印模板盘数独盘面。
        /// </summary>
        public void PrintSudokuTemplate()
        {
            if (this._sudoku_template == null)
            {
                Console.WriteLine("此数独未设置模板盘。");
            }
            else
            {
                this.PrintSudoku(this._sudoku_template);
            }
        }

        /// <summary>
        /// 打印结果盘数独盘面。
        /// </summary>
        public void PrintSudokuResult()
        {
            if (this._sudoku_result == null)
            {
                Console.WriteLine("此数独未设置结果盘。");
            }
            else
            {
                this.PrintSudoku(this._sudoku_result);
            }
        }

        /// <summary>
        /// 打印数独盘面。
        /// </summary>
        /// <param name="sudoku"></param>
        public void PrintSudoku(int[,] sudoku)
        {
            Console.WriteLine("┌─┬─┬─┰─┬─┬─┰─┬─┬─┐");
            for (int i = 0; i < 9; i++)
            {
                Console.Write("│");
                for (int j = 0; j < 9; j++)
                {
                    if ((j + 1) % 3 == 0 && j != 8)
                    {
                        Console.Write("{0} ┃", sudoku[i, j] > 0 ? sudoku[i, j].ToString() : " ");
                    }
                    else
                    {
                        Console.Write("{0} │", sudoku[i, j] > 0 ? sudoku[i, j].ToString() : " ");
                    }
                }
                if (i == 8)
                {
                    Console.WriteLine("\n└─┴─┴─┸─┴─┴─┸─┴─┴─┘");
                }
                else if ((i + 1) % 3 == 0)
                {
                    Console.WriteLine("\n┝━┿━┿━╋━┿━┿━╋━┿━┿━┥");
                }
                else
                {
                    Console.WriteLine("\n├─┼─┼─╂─┼─┼─╂─┼─┼─┤");
                }
            }
            Console.WriteLine();
        }
        #endregion

        #region 【递归求解】
        /// <summary>
        /// 数独求解。
        /// </summary>
        /// <returns></returns>
        public List<int[,]> SolveSudoku()
        {
            return SolveSudoku(this._sudoku_template);
        }

        /// <summary>
        /// 递归求解数独。
        /// </summary>
        /// <param name="sudoku">数独盘面。</param>
        /// <returns></returns>
        public List<int[,]> SolveSudoku(int[,] sudoku)
        {
            List<int[,]> result = new List<int[,]>();
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (sudoku[i, j] == 0)
                    {
                        int[] values = this.GetValues(sudoku, i, j);
                        int[,] _sudoku = (int[,])sudoku.Clone();
                        foreach (int value in values)
                        {
                            _sudoku[i, j] = value;
                            List<int[,]> _result = SolveSudoku(_sudoku);
                            if (_result != null && _result.Count > 0)
                            {
                                result.AddRange(_result);
                            }
                        }
                        return result;
                    }
                }
            }
            result.Add(sudoku);
            return result;
        }

        /// <summary>
        /// 获取数独盘面中，指定位置的可输入的值。
        /// </summary>
        /// <param name="sudoku">数独盘面。</param>
        /// <param name="i"></param>
        /// <param name="j"></param>
        /// <returns></returns>
        private int[] GetValues(int[,] sudoku, int i, int j)
        {
            List<int> values = new List<int>();
            values.AddRange(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
            List<int> _values = new List<int>();
            for (int k = 0; k < 9; k++)
            {
                values.Remove(sudoku[i, k]);//移除横向已经存在的数字。
                values.Remove(sudoku[k, j]);//移除纵向已经存在的数字。
            }
            for (int m = (i / 3) * 3; m < (i / 3) * 3 + 3; m++)
            {
                for (int n = (j / 3) * 3; n < (j / 3) * 3 + 3; n++)
                {
                    values.Remove(sudoku[m, n]);//移除九宫域中已经存在的数字。
                }
            }

            return values.ToArray();
        }

        #endregion

        #region 【挖洞算法】
        /// <summary>
        /// 在终盘中，挖出指定个数的空格，且保证解的唯一性。
        /// </summary>
        /// <param name="count">挖出空格的个数。</param>
        /// <param name="sudoku_end">终盘数独。</param>
        /// <returns></returns>
        private int[,] DigHole(int count, int[,] sudoku_end)
        {
            int[,] sudoku = (int[,])sudoku_end.Clone();
            int[] hole = new int[81];
            for (int i = 0; i < 81; hole[i] = i++) ;
            RandomShuffle<int>(hole);
            for (int i = 0; i < 81; i++)
            {
                int m = hole[i] / 9;
                int n = hole[i] % 9;
                int temp = sudoku[m, n];
                sudoku[m, n] = 0;
                if (SolveSudoku(sudoku).Count != 1)//解的唯一性
                {
                    sudoku[m, n] = temp;//恢复挖洞
                }
                else
                {
                    count--;
                }
                if (count == 0)
                {
                    break;
                }
            }

            return sudoku;
        }
        #endregion

        #region 【随机生成数独终盘】
        /// <summary>
        /// 随机生成一个数独的终盘。
        /// </summary>
        /// <returns></returns>
        public static int[,] RandomSudoku()
        {
            int[,] sudoku = new int[SUDOKU_CONT, SUDOKU_CONT];
            int[] index_I = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
            int[] index_J = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
            int[] randomArray = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

            RandomShuffle<int>(randomArray);

            RandomShuffle<int>(index_I, 0, 2);
            RandomShuffle<int>(index_I, 3, 5);
            RandomShuffle<int>(index_I, 6, 8);

            RandomShuffle<int>(index_J, 0, 2);
            RandomShuffle<int>(index_J, 3, 5);
            RandomShuffle<int>(index_J, 6, 8);

            for (int i = 0; i < SUDOKU_CONT; i++)
            {
                int first = i * 3 + i / 3;
                for (int j = 0; j < SUDOKU_CONT; j++)
                {
                    sudoku[index_I[i], index_J[j]] = randomArray[(first + j) % 9];
                }
            }

            return sudoku;
        }
        #endregion

        #region 【随机化序列元素】
        /// <summary>
        /// 随机化序列元素。
        /// </summary>
        /// <typeparam name="T">元素类型。</typeparam>
        /// <param name="array">元素序列。</param>
        public static void RandomShuffle<T>(T[] array)
        {
            RandomShuffle<T>(array, 0, array.Length - 1);
        }

        /// <summary>
        /// 随机化序列元素。
        /// </summary>
        /// <typeparam name="T">元素类型。</typeparam>
        /// <param name="array">元素序列。</param>
        /// <param name="minIndex">序列起始下标。</param>
        /// <param name="maxIndex">序列结束下标。</param>
        public static void RandomShuffle<T>(T[] array, int minIndex, int maxIndex)
        {
            for (int i = minIndex; i < maxIndex + 1; i++)
            {
                int r = (new Random(Guid.NewGuid().GetHashCode())).Next(minIndex, maxIndex);
                T temp = array[r];
                array[r] = array[i];
                array[i] = temp;
            }
        }
        #endregion

        public bool CheckSudokuResult()
        {
            for (int i = 0; i < 9; i++)
            {
                List<int> values = new List<int>();
                values.AddRange(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
                for (int j = 0; j < 9; j++)
                {
                    if (this.SudokuResult[i, j] == 0 || values.IndexOf(this.SudokuResult[i, j]) == -1)
                    {
                        return false;
                    }
                    else
                    {
                        values.Remove(this.SudokuResult[i, j]);
                    }
                }
            }
            for (int j = 0; j < 9; j++)
            {
                List<int> values = new List<int>();
                values.AddRange(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
                for (int i = 0; i < 9; i++)
                {
                    if (this.SudokuResult[i, j] == 0 || values.IndexOf(this.SudokuResult[i, j]) == -1)
                    {
                        return false;
                    }
                    else
                    {
                        values.Remove(this.SudokuResult[i, j]);
                    }
                }
            }
            for (int m = 0; m < 9; m++)
            {
                List<int> values = new List<int>();
                values.AddRange(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
                for (int n = 0; n < 9; n++)
                {
                    int i = m / 3 * 3 + n / 3;
                    int j = m % 3 * 3 + n % 3;
                    if (this.SudokuResult[i, j] == 0 || values.IndexOf(this.SudokuResult[i, j]) == -1)
                    {
                        return false;
                    }
                    else
                    {
                        values.Remove(this.SudokuResult[i, j]);
                    }
                }
            }
            return true;
        }
    }

    #region 【数独难度级别】
    /// <summary>
    /// 数独难度级别。
    /// </summary>
    public enum Level
    {
        Level1 = 1,
        Level2 = 2,
        Level3 = 3,
        Level4 = 4
    }
    #endregion
}
